<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 先建立一棵树
      function node(obj) {
        var newobj = {}
        if (obj.length == 1) {
          newobj.value = obj[0]
        } else if (obj.length == 0) {
          newobj.value == null
        } else {
          newobj.left = node(obj[0])
          newobj.value = obj[1]
          newobj.right = node(obj[2])
        }
        return newobj
      }

      var root = node([[[[7], 11, [2]], 4, []], 5, [[13], 8, [[], 4, [1]]]])

      console.log('🚀🚀🚀wimi======>>>root',root)

      // 中序遍历
      function goTree1(tree) {
        if (tree.hasOwnProperty('left')) {
          goTree1(tree.left)
          console.log(tree.value)
          goTree1(tree.right)
        } else {
          tree.value == null ? console.log('') : console.log(tree.value)
        }
      }
      console.log('===============中序遍历=====================');
      goTree1(root)
      console.log('===============中序遍历=====================');

      // 前序遍历
      function goTree2(tree) {
        tree.value == null ? console.log('') : console.log(tree.value)
        if (tree.hasOwnProperty('left')) {
          goTree2(tree.left)
          goTree2(tree.right)
        }
      }

      console.log('===============前序遍历=====================');
      goTree2(root)
      console.log('===============前序遍历=====================');

      // 后序遍历
      function goTree3(tree) {
        if (tree.hasOwnProperty('left')) {
          goTree3(tree.left)
          goTree3(tree.right)
          console.log(tree.value)
        } else {
          tree.value == null ? console.log('') : console.log(tree.value)
        }
      }

      console.log('===============后序遍历=====================');
      goTree3(root)
      console.log('===============后序遍历=====================');

      //层序遍历
      // 层序遍历需要使用队列的数据结构，这里可以用数组来替代
      // 这里不能使用迭代
      function goTree4(tree) {
        let deque = []
        deque.push(root)
        while (deque.length != 0) {
          front = deque.shift()
          if (front.hasOwnProperty('left')) {
            deque.push(front.left)
            deque.push(front.right)
          }
          front.value == null ? console.log('') : console.log(front.value)
        }
      }

      console.log('===============层序遍历=====================');
      goTree4(root)
      console.log('===============层序遍历=====================');
    </script>
  </body>
</html>
